package 题目集.线段树or树状数组.树状数组;

import java.io.*;
import java.util.Arrays;

/**
 * todo：多练
 * 单次查询范围内的种类
 * https://www.luogu.com.cn/problem/P1972
 * 朴素思路：
 *      对于每一个查询，都去跑一次，用bitset对种类去重。
 * 树状数组（离线）思路：
 *      我们查询[l,r]的种类个数。
 *      可以看作r之前出现的所有数的最后位置，有多少个在l之后。
 *      我们可以维护一个最后位置表，当遇到一个未出现的数，在该位置+1，遇到个已出现的数，对之前出现的位置-1.
 *      这个表每次需要维护到r位置。当维护好后，我们查询这个表中[l,r]的和。
 *      而这个表可以用树状数组维护
 */
public class ch06_范围内的种类_离线算法 {
    static int maxN = (int) (1e6 + 10);
    static int n, m;
    static int[] tree = new int[maxN];
    static int[] origin;
    static int[] lasts = new int[maxN];  //记录每个颜色最后一次出现的位置

    public static void main(String[] args) {
        Reader sc = new Reader();
        n = sc.nextInt();
        origin = new int[n + 1];
        for (int i = 1; i < origin.length; i++) {
            origin[i] = sc.nextInt();
        }
        m = sc.nextInt();
        int[][] query = new int[m + 1][3];  //0原下标，1:l,2:r
        int[] res = new int[m + 1];
        for (int i = 1; i < query.length; i++) {
            query[i][0] = i;
            query[i][1] = sc.nextInt();
            query[i][2] = sc.nextInt();
        }
        Arrays.sort(query, (a, b) -> a[2] - b[2]);
        int i = 1;
        for (int[] q : query) {
            while (i <= q[2]) {
                int color = origin[i];
                if (lasts[color] != 0) {
                    add(lasts[color], -1);
                }
                lasts[color] = i;
                add(i, 1);
                i++;
            }
            res[q[0]] = range(q[1], q[2]);
        }
        for (int j = 1; j < res.length; j++) {
            Reader.pw.println(res[j]);
        }
        Reader.pw.flush();
    }

    private static void add(int i, int v) {
        while (i <= n) {
            tree[i] += v;
            i += lowbit(i);
        }
    }

    public static int range(int l, int r) {
        return query(r) - query(l - 1);
    }

    public static int query(int i) {
        int res = 0;
        while (i > 0) {
            res += tree[i];
            i -= lowbit(i);
        }
        return res;
    }

    public static int lowbit(int x) {
        return x & -x;
    }

    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in));
        static PrintWriter pw=new PrintWriter(new BufferedOutputStream(System.out));

        public Reader(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }

}
